/*
Date:20210418 0:11pm
key:用例过不好
*/
class Solution {
public:
    bool youxu(string &s)
    {
        for(int i=s.size()-1;i>0;i--)
        {
            if(s[i-1]>s[i])
            {
                return 0;
            }
        }
        return 1;
    }
    void swap(char&a,char&b)
    {
        char c;
        c=a;
        a=b;
        b=c;
    }
    void res(string &s,int i)
    {
        int j=s.size()-1;
        while(i<j){swap(s[i],s[j]);i++;j--;}
    }
    int find_i(string &s)
    {
        for(int i=s.size()-1;i>0;i--)
        {
            if(s[i-1]>s[i])
            {
                return i;
            }
        }
        return 0;
    }
    bool F(string &s,int &i, int&j)
    {
         for(int k=i;k<=j;k++)
        {
             if(s[k] >= s[i - 1])
             {
                 return false;
             }
         }
        return true;
    }
    //找到 最大下标 j ，使得 i <= j < s.length 且对于所有在闭区间 [i, j] 之间的 k 都有 s[k] < s[i - 1] 。
        int find_j(string &s,int &i)
    {
        for(int j=s.size()-1;j>=i;j--)
        {
            if(F(s,i,j))
            {
                return j;
            }
        }
        return 0;
    }
    void F1(string&s)
    {
        int i=find_i(s);
        int j=find_j(s,i);
        swap(s[i-1],s[j]);
        res(s,i);
    }
    int makeStringSorted(string s) {
    int count=0;
        while(1)
        {
            F1(s);
            count=count%(1000000007)+1;
            if(youxu(s))
            {
                break;
            }
            
        }
        return count%(1000000007);
    }
};